/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package model;

import java.text.DateFormat;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Calendar;
import java.util.Date;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import util.Matematica;

/**
 *
 * @author Enrique
 */
public class Algoritmo {
    
    // ATRIBUTOS
    
    public static final long HORA_MILI = 3600*1000;  //constante para horas (en milisegundos)
    
    // NO USAR ESTA CLASE TODAVIA, ESTA SIENDO MODIFICADA
    
    // METODOS 
    
    // metodo para obtener el nodo con el menor F de la lista de abiertos
    public static Nodo obtenerNodoMenorF(List<Nodo> listaNodosAbiertos){
        Nodo nodoMinimo = listaNodosAbiertos.get(0);    // empiezo con el primero de la lista
        
        for (int i=1; i < listaNodosAbiertos.size(); i++){  // para cada uno de los otros nodos de la lista
            if (listaNodosAbiertos.get(i).getF() < nodoMinimo.getF())   // si este nodo tiene un F menor que el minimo hasta el momento
                nodoMinimo = listaNodosAbiertos.get(i);     // se vuelve en el nuevo nodo con menor F
        }
        
        return nodoMinimo;
    }
    
    // metodo para reconstruir el camino entre nodo origen y destino, una vez encontrado este ultimo al final del algoritmo
    public static void reconstruirCamino(Nodo origen, Nodo destino, Paquete paquete){
        
        String camino = "";
        Nodo actual = destino;  //empiezo analizando el nodo destino
        String idVueloActual = "";
        Vuelo vueloActual = null;
        SimpleDateFormat formato = new SimpleDateFormat("HH:mm");
        double horasViaje = 0;   //minutos totales empleados en el viaje
        double tiempoVuelo;    // tiempo del vuelo
        double tiempoEspera;      //tiempo de espera
        
        
        while (actual.getCiudad().getOaci().equals(origen.getCiudad().getOaci()) == false){ //mientras no se haya llegado al nodo origen
            // actualizo el camino
            vueloActual = actual.getAristaPadre().getVuelo();   //obtengo el vuelo usado para llegar al nodo actual
            
            HistorialVuelo historialVueloTemp = Algoritmo.obtenerFechaVueloTomada(actual.getFechaLlegada(),vueloActual);
            //paquete.getHistorialVuelos().add(Algoritmo.obtenerFechaVueloTomada(actual.getFechaLlegada(),vueloActual));  // agrego al paquete el historialVuelo que se tomo para llegar al nodo actual
            paquete.getHistorialVuelos().add(historialVueloTemp);
            historialVueloTemp.getPaquetes().add(paquete);
            historialVueloTemp.setNumPaquetes(historialVueloTemp.getNumPaquetes() + 1);
                        
            actual = actual.getNodoPadre(); // actualizo el nodo actual para que apunte a su padre
           
        }        
        
    }
    
    // metodo para obtener lista de nodos vecinos al nodo actual
    public static List<Nodo> obtenerListaNodosVecinos(Nodo actual){
        
        List<Nodo> listaNodosVecinos = new ArrayList<Nodo>();
        
        for (int i=0; i < actual.getListaAristasOrigen().size(); i++){  //para cada una de las aristas vecinas del nodo actual
            if (listaNodosVecinos.contains(actual.getListaAristasOrigen().get(i).getNodoFinal()) == false){ // si el nodo final de esa arista no esta en la lista de nodos vecinos
                listaNodosVecinos.add(actual.getListaAristasOrigen().get(i).getNodoFinal());    // aÃ±ado dicho nodo a la lista de nodos vecinos
            }
        }
        
        return listaNodosVecinos;
    }
    
    // metodo para hallar la "distancia" o costo de tiempo al recorrer una arista
    public static double costoArista(Arista aristaTentativa, Date fechaLlegada){
        
        double tiempoTotal = 0;     // tiempo total de viaje
        double tiempoEspera = 0;    // tiempo de espera entre llegar al nodo inicial y tomar el vuelo
        double tiempoVuelo = 0;     // tiempo del vuelo
        Nodo origen = aristaTentativa.getNodoInicial();     // obtengo el nodo origen de la arista
        Nodo destino = aristaTentativa.getNodoFinal();      // obtengo el nodo destino de la arista
        
        tiempoVuelo = Algoritmo.diferenciaHoras(aristaTentativa.getVuelo().getHoraPartida().getTime() + (long)(origen.getCiudad().getDiferenciaHora()*HORA_MILI),
                    aristaTentativa.getVuelo().getHoraLlegada().getTime() + (long)(destino.getCiudad().getDiferenciaHora()*HORA_MILI));    //calculo el tiempo del vuelo (usando la diferencia en horas con lima como base)
        //tiempoEspera = Algoritmo.diferenciaHoras(origen.getFechaLlegada().getTime(), aristaTentativa.getVuelo().getHoraPartida().getTime());    // calculo el tiempo de espera, para el vuelo mas proximo, en el nodo padre
        tiempoEspera = (Algoritmo.obtenerTiempoPartidaMasProximo(aristaTentativa.getVuelo(),fechaLlegada) - fechaLlegada.getTime())/HORA_MILI;    // calculo el tiempo de espera para el vuelo mas proximo en el nodo padre
        tiempoTotal = tiempoVuelo + tiempoEspera;   // obtengo el tiempo total de viaje
        
        return tiempoTotal;
    }
    
    // metodo para encontrar la arista con menor costo entre 2 nodos
    public static Arista encontrarAristaTentativa(Nodo actual, Nodo vecino){
        Arista resultado = new Arista();        //resultado final a devolver
        List<Arista> listaAristasPosibles = new ArrayList<Arista>();    // lista de las aristas entre ambos nodos
        double costoMinimo = Double.MAX_VALUE;     //el costo minimo entre las aristas
        double costo;
        
        //obtengo solamente las aristas entre ambos nodos
        for (int i=0; i < actual.getListaAristasOrigen().size(); i++){  // para cada una de las aristas que parten del nodo actual (origen)
            if (actual.getListaAristasOrigen().get(i).getNodoFinal().equals(vecino)){   // si el nodo final de esa arista es el nodo vecino (destino)
                listaAristasPosibles.add(actual.getListaAristasOrigen().get(i));    // la aÃ±ado a la lista de aristas posibles
            }
        }
        
        //obtengo la arista con menor costo
        for (int i=0; i < listaAristasPosibles.size(); i++){    // para cada una de las aristas posibles
            costo = costoArista(listaAristasPosibles.get(i),actual.getFechaLlegada());
            if (costo < costoMinimo){    // si el costo de esta arista es menor que el minimo hasta el momento
                resultado = listaAristasPosibles.get(i);    // se vuelve en la mejor hasta el momento:
                costoMinimo = costo;    // actualizo el nuevo costo minimo
            }
        }
        
        
        return resultado;
    }
    
    // metodo para calcular la diferencia (en horas) entre 2 horas (considerando si son de distintos dias)
    public static double diferenciaHoras(long inicio, long fin)    {
        double diferencia = Math.abs(fin - inicio) ;
            if (fin < inicio){
                return 24 - (diferencia / (3600 * 1000)%24);
            }
            else return diferencia / (3600 * 1000)%24;
    }
        
    // metodo que ejecuta el algorimto A* principal con un paquete en particular
    public static void algoritmoAEstrella(Simulacion simu, Paquete paquete){
        String ruta = null;
        String destinoAbrev = null;
        double gTentativo = 0;
        Arista aristaTentativa = new Arista();
        List<Nodo> listaNodosCerrados = new ArrayList<Nodo>();
        List<Nodo> listaNodosAbiertos = new ArrayList<Nodo>();
        Nodo actual = new Nodo();
        Nodo vecino = new Nodo();
        List<Nodo> listaNodosVecinos = new ArrayList<Nodo>();
        
        destinoAbrev = paquete.getCiudadByIdCiudadDestino().getAbreviacion();
        
        // calculo funcion H
        Algoritmo.calcularH(destinoAbrev, simu);
        Nodo origen = Nodo.buscarNodoPorAbrev(paquete.getCiudadByIdCiudadOrigen().getAbreviacion(),simu.getListaNodos());
        DateFormat formatoFecha = new SimpleDateFormat("HH:mm");
        Date llegada = paquete.getFechaHoraRecepcion();
        origen.setFechaLlegada(llegada);
        Nodo destino = Nodo.buscarNodoPorAbrev(destinoAbrev,simu.getListaNodos());
        origen.setG(0);
        origen.setF(origen.getG() + origen.getH());
        listaNodosAbiertos.add(origen);
        
        while (listaNodosAbiertos.size() > 0){  //mientras la lista de nodos abiertos no este vacia
            listaNodosVecinos.clear();  //limpio la lista de nodos vecinos
            
            actual = Algoritmo.obtenerNodoMenorF(listaNodosAbiertos);   //obtengo el nodo, de la lista de abiertos, con el menor F. Ese sera el actual
            //System.out.println(actual.getCiudad().getCiudad());
            if (actual.getCiudad().getOaci().equals(destino.getCiudad().getOaci())){    // si el nodo actual es el nodo destino
                Algoritmo.reconstruirCamino(origen,destino,paquete);    // encontre el destino, ahora reconstruyo el camino a tomar, fin de algoritmo
            }
            
            
            
            listaNodosCerrados.add(actual); // aÃ±ado el nodo actual a la lista de cerrados
            listaNodosAbiertos.remove(actual);  // quito el nodo actual de la lista de abiertos
            listaNodosVecinos = Algoritmo.obtenerListaNodosVecinos(actual); //obtengo la lista de nodos vecinos al nodo actual
            for (int i=0; i < listaNodosVecinos.size(); i++){   //para cada uno de los nodos vecinos
                vecino = listaNodosVecinos.get(i);  //obtengo el nodo vecino bajo analisis actualemte
                if (listaNodosCerrados.contains(vecino)){ // si este nodo vecino esta en la lista de cerrados
                    continue;   // lo ignoro y evaluo el siguiente
                }
                
                aristaTentativa = Algoritmo.encontrarAristaTentativa(actual,vecino);  //encuentro el mejor vuelo entre el nodo actual y el vecino
                gTentativo = vecino.getG() + costoArista(aristaTentativa,actual.getFechaLlegada()); //obtengo un valor tentativo de G para el nodo vecino
                if ((listaNodosAbiertos.contains(vecino) == false)    // si el vecino no esta en la lista de abiertos
                        || (gTentativo < vecino.getG())){     // o si el valor tentativo de G calculado es menor que su G actual
                    vecino.setNodoPadre(actual); //su nuevo padre sera el nodo actual
                    vecino.setG(gTentativo);  // su valor G sera el tentativo calculado previamente
                    vecino.setF(vecino.getG() + vecino.getH());   //calculo su nuevo valor F
                    vecino.setAristaPadre(aristaTentativa);     // le asigno como arista padre la tentativa
                    Calendar fechaLlegada = Calendar.getInstance();
                    fechaLlegada.setTime(actual.getFechaLlegada());
                    double tiempoDouble = costoArista(aristaTentativa,actual.getFechaLlegada());
                    //System.out.println(tiempoDouble);
                    fechaLlegada.add(Calendar.HOUR_OF_DAY, (int)tiempoDouble);
                    //System.out.println((int)tiempoDouble);
                    fechaLlegada.add(Calendar.MINUTE, (int)((tiempoDouble*60)%60));
                    //System.out.println((int)((tiempoDouble*60)%60));
                    //vecino.setFechaLlegada(aristaTentativa.getVuelo().getHoraLlegada());    // le asigno la hora en que se llego a ese nodo, usando su arista padre
                    vecino.setFechaLlegada(fechaLlegada.getTime());
                    if (listaNodosAbiertos.contains(vecino) == false){  // si el nodo vecino no esta en la lista de abiertos
                        listaNodosAbiertos.add(vecino); // lo aÃ±ado a la lista de abiertos
                    }
                }
                
            }
        }
        Algoritmo.limpiarEstructuras(simu);
        
    }
        
    // metodo para calcular el H de los nodos (funcion heuristica) en base al destino
    public static void calcularH(String destinoAbrev, Simulacion simu){
        
        // obtengo la ciudad correspondiente al parametro del metodo
        Ciudad destino = Nodo.buscarNodoPorAbrev(destinoAbrev,simu.getListaNodos()).getCiudad();
        
        // calculo maxima velocidad de vuelos de aviones        
        double velocidadMaxima = 0;
        double distancia = 0;
        double velocidad = 0;
        
        for (int i=0; i < simu.getListaAristas().size(); i++){  //para cada uno de los vuelos
            distancia = Matematica.distanciaEntrePuntos(simu.getListaAristas().get(i).getNodoInicial().getCiudad(),simu.getListaAristas().get(i).getNodoFinal().getCiudad()); //calculo distancia recorrida en ese vuelo
            velocidad = (distancia/4)/60;    //calculo velocidad de ese vuelo (km/minutos)
            
            if (velocidad > velocidadMaxima)    // si la nueva velocidad es mayor que la maxima hasta el momento
                velocidadMaxima = velocidad;    // la nueva velocidad maxima es esta velocidad
        }
        
        // calculos los H
        
        for (int i=0; i<simu.getListaNodos().size(); i++){  //para cada uno de los nodos
            simu.getListaNodos().get(i).setH(Matematica.distanciaEntrePuntos(destino, simu.getListaNodos().get(i).getCiudad()) / velocidadMaxima);   // les asigno su valor H
        }
        
    }
            
    // FALTA metodo para "limpiar" algunas partes de las estructuras de datos usadas durante la ejecucion del algoritmo
    public static void limpiarEstructuras(Simulacion simu){
        
        // elimino/reseteo los atributos "fechaLlegada", g, f y h de los nodos
        
        for (int i=0; i<simu.getListaNodos().size(); i++){
            Nodo nodoTemp = simu.getListaNodos().get(i);
            nodoTemp.setFechaLlegada(null);
            nodoTemp.setG(0);
            nodoTemp.setF(0);
            nodoTemp.setH(0);
        }
        
    }

    // metodo para obtener la hora de partida mas cercana a una fecha dada
    public static long obtenerTiempoPartidaMasProximo(Vuelo vuelo, Date fechaLlegada) {
        
        Set fechasVuelos = vuelo.getHistorialVuelos();      // obtengo el set con hitorial de vuelos de ese vuelo
        HistorialVuelo historialVueloTemp;
        Iterator<HistorialVuelo> i = fechasVuelos.iterator();   // iterador del set de HistorialVuelo
        Date menorFecha = new Date(Long.MAX_VALUE);     // la menor fecha posible
                
        while(i.hasNext()){// mientras hayan fechas para ese vuelo
            historialVueloTemp = i.next();  //obtengo el siguiente historial de vuelo
            
            if (historialVueloTemp.getNumPaquetes() >= vuelo.getCapMax()){  // si el vuelo en esa fecha ya no tiene espacio disponible
                continue;   // evaluo el siguiente
            }
            
            //if ((historialVueloTemp.getId().getFecha().compareTo(menorFecha) >= 0)      // si la fecha de ese vuelo es igual o posterior a la de la menor fecha hasta ahora
            if ((historialVueloTemp.getId().getFecha().compareTo(menorFecha) < 0)
                && (historialVueloTemp.getId().getFecha().compareTo(fechaLlegada) >= 0)){     // y la fecha de ese vuelo es posterior o igual a la fecha de llegada a esa ciudad
                menorFecha = historialVueloTemp.getId().getFecha(); // actualizo la menor fecha
            }
            
        }    
        
        return menorFecha.getTime();
        
    }

    // metodo para obtener el vuelo que se tomo para llegar en la fecha llegada
    public static HistorialVuelo obtenerFechaVueloTomada(Date fechaLlegada, Vuelo vueloActual) {
        
        Set fechasVuelos = vueloActual.getHistorialVuelos();    // obtengo la lista de historiales de ese vuelo
        Iterator<HistorialVuelo> i = fechasVuelos.iterator();   // iterador del set de HistorialVuelo
        HistorialVuelo historialVueloTemp;
        Date fechaMasCercana = new Date(Long.MIN_VALUE);     // valor inicial de la fecha mas cercana
        HistorialVuelo historialVueloMasCercano = null;
        
        while (i.hasNext()){   //mientras hayan fechas para ese vuelo
            historialVueloTemp = i.next();  //obtengo el siguiente historial de vuelo
            
//            if ((historialVueloTemp.getId().getFecha().compareTo(fechaMasCercana) > 0)  // si la fecha de ese vuelo es mayor que la fechaMasCercana
//                && (historialVueloTemp.getId().getFecha().compareTo(fechaLlegada)) < 0){    // y si la fecha de ese vuelo es menor que la fecha de llegada
//                fechaMasCercana = historialVueloTemp.getId().getFecha();    // actualizo fechaMasCercana
//                historialVueloMasCercano = historialVueloTemp;      // actualizo historialVueloMasCercano
//            }
            if ((historialVueloTemp.getId().getFecha().compareTo(fechaMasCercana) > 0)  // si la fecha de ese vuelo es mayor que la fechaMasCercana
                && (historialVueloTemp.getId().getFecha().compareTo(fechaLlegada)) < 0
                && (historialVueloTemp.getNumPaquetes() <= vueloActual.getCapMax())){    // y si la fecha de ese vuelo es menor que la fecha de llegada
                fechaMasCercana = historialVueloTemp.getId().getFecha();    // actualizo fechaMasCercana
                historialVueloMasCercano = historialVueloTemp;      // actualizo historialVueloMasCercano
            }
            
        }
        
        return historialVueloMasCercano;
    }
    
}
    